//
// Created by REEJI2219 on 2024-09-12.
//
#include <iostream>
#include <cmath>
using namespace std;
class TreeNode {
public:
    int data;
    TreeNode *left;TreeNode *right;
    int lfg;
    int rfg;
    TreeNode() {
        left = nullptr;
        right = nullptr;
        data = 0;
        lfg = 0;
        rfg = 0;
    }

    /**
     * 先序遍历
     */
    void preRootPrint() {
        cout<<data<<endl;
        if(left) {
            left->preRootPrint();
        }
        if(right) {
            right->preRootPrint();
        }
    }

    /**
     * 中序遍历
     */
    void centerRootPrint() {
        if(left) {
            left->centerRootPrint();
        }
        cout<<data<<endl;
        if(right) {
            right->centerRootPrint();
        }
    }

    /**
     * 后续遍历
     */
    void rightRootPrint() {
        if(left) {
            left->rightRootPrint();
        }
        if(right) {
            right->rightRootPrint();
        }
        cout<<data<<endl;
    }

    void addData(int data) {
        if(data<this->data) {
            if(left) {
                left->addData(data);
            }else {
                TreeNode *node = new TreeNode();
                node->data = data;
                left = node;
            }
        }else {
            if(right) {
                right->addData(data);
            }else {
                TreeNode *node = new TreeNode();
                node->data = data;
                right = node;
            }
        }
    }

};
class BinaryTree {
private:
    TreeNode * root;
    TreeNode *pre;
    TreeNode *result;
public:
    BinaryTree(int data) {
        root = new TreeNode();
        root->data = data;
    }
    // void add(int data) {
    //     TreeNode *current  = root;
    //     while (current!=nullptr) {
    //         if(data<current->data) {
    //             if(current->left) {
    //                 current = current->left;
    //             }else {
    //                 TreeNode *node = new TreeNode();
    //                 node->data = data;
    //                 current->left = node;
    //                 return;
    //             }
    //         }else {
    //             if(current->right) {
    //                 current = current->right;
    //             }else {
    //                 TreeNode *node = new TreeNode();
    //                 node->data = data;
    //                 current->right = node;
    //                 return;
    //             }
    //         }
    //     }
    // }
    void add(int data) {
        root->addData(data);
    }
    void preRootPrint() {
        root->preRootPrint();
    }
    void centerRootPrint() {
        root->centerRootPrint();
    }
    void rightRootPrint() {
        root->rightRootPrint();
    }
    //先序遍历二叉树构建线索二叉树
    void buildInfoTreePreRootVisit() {
        buildInfoTreePreRootVisit(root);
        pre->right=nullptr;
    }
    //寻找前驱节点
    void findPreNode(int data) {
        findPreNode(root,data);
        printf("p_node is %d",result->data);
    }
   void findPreNode(TreeNode *node,int data) {
        //空指针，直接返回
        if(node==nullptr) {
            return ;
        }
        //只是为了方便打印
        if(pre==nullptr) {
            printf("current %d pre is null;\n",node->data);
        }else {
            printf("current %d pre is %d;\n",node->data,pre->data);
        }
        //相等时，此时的数据就是前驱
        if(node->data == data) {
            result = pre;
        }else {
            pre = node;
        }
        findPreNode(node->left,data);
        findPreNode(node->right,data);

    }
    void buildInfoTreePreRootVisit(TreeNode *tree_node) {
        if(tree_node!=nullptr) {
            visit(tree_node);
            if(tree_node->lfg==0) {
                buildInfoTreePreRootVisit( tree_node->left);
            }
            if(tree_node->rfg==0) {
                buildInfoTreePreRootVisit( tree_node->right);
            }

        }
    }
    void visit(TreeNode *tree_node) {
        cout<<tree_node->data<<endl;
        //左孩子没有，左孩子为前驱
        if(tree_node->left==nullptr) {
            tree_node->left = pre;
            tree_node->lfg=1;
        }
        //右边孩子没有，右孩子为后继，注意是下一层
        if(pre!=nullptr&&pre->right==nullptr) {
            pre->right = tree_node;
            pre->rfg = 1;
        }
        pre = tree_node;
    }
    void showPreAndAfter(TreeNode *tree_node) {
        if(tree_node!=nullptr) {
            if(tree_node->right!=nullptr) {
                printf("current:%d left_type:%d left_data:%d right_type:%d right_data:%d \n",tree_node->data,tree_node->lfg,tree_node->left->data,tree_node->rfg,tree_node->right->data);
            }else {
                printf("current:%d left_type:%d left_data:%d right_type:%d right_data is null",tree_node->data,tree_node->lfg,tree_node->left->data,tree_node->rfg);
            }

            if(tree_node->lfg==0) {
                showPreAndAfter(tree_node->left);
            }
            if(tree_node->rfg==0) {
                showPreAndAfter(tree_node->right);
            }
        }
    }
    void findInfoPreNode(int data) {
        pre = nullptr;
        result = nullptr;
    }
    void findInfoPreNode(TreeNode *node ,int data) {

        if(node->data = data) {
            if(node->rfg=1) {
                result = node->right;
                return;
            }
        }

    }
    TreeNode *getRoot() {
        return root;
    }

};

// int main(int argc, char *argv[]) {
//     BinaryTree *binaryTree = new BinaryTree(10);
//     binaryTree->add(5);
//     binaryTree->add(12);
//     binaryTree->add(7);
//     binaryTree->add(3);
//     binaryTree->add(8);
//     binaryTree->add(2);
//     // binaryTree->preRootPrint();
//     // binaryTree->findPreNode(2);
//     // printf("线索树构建 \n");
//     binaryTree->buildInfoTreePreRootVisit();
//     binaryTree->showPreAndAfter(binaryTree->getRoot());
//     // binaryTree->rightPrint();
//     // binaryTree->parentPrint();
// }
